use std::fmt;
use num_traits::Num;

/// Common trait for all grid graph types
///
/// This trait provides a unified interface for computing maximum flow and
/// querying results across different grid graph implementations (2D/3D,
/// different connectivity patterns, single/multi-threaded).
///
/// # Type Parameters
///
/// * `TerminalCap` - Type for terminal edge capacities (source/sink connections)
/// * `NeighborCap` - Type for neighbor edge capacities (grid connections)
/// * `Flow` - Type for accumulated flow value
///
/// # Examples
///
/// ```rust
/// use grid_cut_rs::{GridGraph2D4C, GridGraph};
///
/// fn process_graph<G>(graph: &mut G) -> G::Flow
/// where
///     G: GridGraph,
/// {
///     graph.compute_maxflow();
///     graph.get_flow()
/// }
///
/// # fn main() -> Result<(), Box<dyn std::error::Error>> {
/// let mut graph = GridGraph2D4C::<i32, i32, i32>::new(10, 10)?;
/// // ... set up capacities ...
/// let flow = process_graph(&mut graph);
/// # Ok(())
/// # }
/// ```
pub trait GridGraph {
    /// Type for terminal edge capacities (source/sink connections)
    type TerminalCap: Num + Copy + PartialOrd;
    
    /// Type for neighbor edge capacities (grid connections)
    type NeighborCap: Num + Copy + PartialOrd;
    
    /// Type for accumulated flow value
    type Flow: Num + Copy + PartialOrd;
    
    /// Computes the maximum flow from source to sink
    ///
    /// This method executes the Boykov-Kolmogorov algorithm to find the
    /// maximum flow through the graph. After completion, use `get_flow()`
    /// to retrieve the flow value and `get_segment()` to query node segments.
    ///
    /// # Examples
    ///
    /// ```rust,no_run
    /// use grid_cut_rs::{GridGraph2D4C, GridGraph};
    ///
    /// # fn main() -> Result<(), Box<dyn std::error::Error>> {
    /// let mut graph = GridGraph2D4C::<i32, i32, i32>::new(10, 10)?;
    /// // ... set up capacities ...
    /// graph.compute_maxflow();
    /// # Ok(())
    /// # }
    /// ```
    fn compute_maxflow(&mut self);
    
    /// Returns the computed maximum flow value
    ///
    /// This method returns the total flow from source to sink computed by
    /// the most recent call to `compute_maxflow()`. If `compute_maxflow()`
    /// has not been called, returns zero.
    ///
    /// # Examples
    ///
    /// ```rust,no_run
    /// use grid_cut_rs::{GridGraph2D4C, GridGraph};
    ///
    /// # fn main() -> Result<(), Box<dyn std::error::Error>> {
    /// let mut graph = GridGraph2D4C::<i32, i32, i32>::new(10, 10)?;
    /// // ... set up capacities ...
    /// graph.compute_maxflow();
    /// let flow = graph.get_flow();
    /// println!("Maximum flow: {}", flow);
    /// # Ok(())
    /// # }
    /// ```
    fn get_flow(&self) -> Self::Flow;
    
    /// Returns the segment (Source or Sink) that a node belongs to
    ///
    /// After computing maximum flow, each node is classified as belonging
    /// to either the source segment or the sink segment. This classification
    /// represents the minimum cut.
    ///
    /// # Parameters
    ///
    /// * `node_id` - The node identifier (obtained from `node_id()` method)
    ///
    /// # Examples
    ///
    /// ```rust,no_run
    /// use grid_cut_rs::{GridGraph2D4C, GridGraph, Segment};
    ///
    /// # fn main() -> Result<(), Box<dyn std::error::Error>> {
    /// let mut graph = GridGraph2D4C::<i32, i32, i32>::new(10, 10)?;
    /// // ... set up capacities ...
    /// graph.compute_maxflow();
    /// 
    /// let node = graph.node_id(5, 5)?;
    /// let segment = graph.get_segment(node);
    /// match segment {
    ///     Segment::Source => println!("Foreground"),
    ///     Segment::Sink => println!("Background"),
    /// }
    /// # Ok(())
    /// # }
    /// ```
    fn get_segment(&self, node_id: usize) -> Segment;
}

/// Error types for GridCut operations
///
/// All fallible operations in the GridCut library return `Result<T, GridCutError>`.
/// This enum covers all possible error conditions that can occur during graph
/// construction and manipulation.
///
/// # Examples
///
/// ```rust
/// use grid_cut_rs::{GridGraph2D4C, GridCutError};
///
/// // Invalid dimensions error
/// let result = GridGraph2D4C::<i32, i32, i32>::new(0, 10);
/// assert!(matches!(result, Err(GridCutError::InvalidDimensions { .. })));
///
/// // Invalid coordinates error
/// let graph = GridGraph2D4C::<i32, i32, i32>::new(10, 10).unwrap();
/// let result = graph.node_id(10, 5);
/// assert!(matches!(result, Err(GridCutError::InvalidCoordinates { .. })));
/// ```
#[derive(Debug, Clone, PartialEq, Eq)]
pub enum GridCutError {
    /// Invalid grid dimensions provided
    ///
    /// This error occurs when attempting to create a graph with zero or negative dimensions.
    /// All dimensions must be positive (> 0).
    InvalidDimensions { width: usize, height: usize },
    
    /// Invalid node ID accessed
    ///
    /// This error occurs when attempting to access a node with an ID that is out of bounds.
    /// Node IDs are internal identifiers and should be obtained through `node_id()` method.
    InvalidNodeId { node_id: usize, max: usize },
    
    /// Invalid coordinates provided
    ///
    /// This error occurs when coordinates are outside the grid bounds.
    /// For 2D grids: x must be in [0, width) and y must be in [0, height).
    /// For 3D grids: z must be in [0, depth).
    InvalidCoordinates {
        x: usize,
        y: usize,
        z: Option<usize>,
    },
    
    /// Invalid offset for neighbor access
    ///
    /// This error occurs when attempting to set neighbor capacity with an invalid offset.
    /// Valid offsets depend on the connectivity type:
    /// - 4-connected: (-1,0), (1,0), (0,-1), (0,1)
    /// - 8-connected: All combinations of {-1,0,1} x {-1,0,1} except (0,0)
    /// - 6-connected: (-1,0,0), (1,0,0), (0,-1,0), (0,1,0), (0,0,-1), (0,0,1)
    InvalidOffset {
        offset_x: i32,
        offset_y: i32,
        offset_z: Option<i32>,
    },
    
    /// Capacity array length doesn't match grid size
    ///
    /// This error occurs when calling `set_caps()` with arrays that don't match
    /// the grid size. All capacity arrays must have length equal to width * height
    /// (or width * height * depth for 3D grids).
    InvalidCapacityArrayLength { expected: usize, actual: usize },
    
    /// Memory allocation failed
    ///
    /// This error occurs when the system cannot allocate sufficient memory for
    /// the graph structure. This is rare but can happen with very large grids.
    AllocationFailed,
}

impl fmt::Display for GridCutError {
    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
        match self {
            GridCutError::InvalidDimensions { width, height } => {
                write!(
                    f,
                    "Invalid grid dimensions: width={}, height={}",
                    width, height
                )
            }
            GridCutError::InvalidNodeId { node_id, max } => {
                write!(
                    f,
                    "Invalid node ID: {} (maximum allowed: {})",
                    node_id, max
                )
            }
            GridCutError::InvalidCoordinates { x, y, z } => {
                if let Some(z_val) = z {
                    write!(f, "Invalid coordinates: ({}, {}, {})", x, y, z_val)
                } else {
                    write!(f, "Invalid coordinates: ({}, {})", x, y)
                }
            }
            GridCutError::InvalidOffset {
                offset_x,
                offset_y,
                offset_z,
            } => {
                if let Some(z_val) = offset_z {
                    write!(f, "Invalid offset: ({}, {}, {})", offset_x, offset_y, z_val)
                } else {
                    write!(f, "Invalid offset: ({}, {})", offset_x, offset_y)
                }
            }
            GridCutError::InvalidCapacityArrayLength { expected, actual } => {
                write!(
                    f,
                    "Invalid capacity array length: expected {}, got {}",
                    expected, actual
                )
            }
            GridCutError::AllocationFailed => {
                write!(f, "Memory allocation failed")
            }
        }
    }
}

impl std::error::Error for GridCutError {}

/// Segment classification after max-flow computation
///
/// After computing the maximum flow, each node in the graph is classified as
/// belonging to either the source segment or the sink segment. This classification
/// represents the minimum cut that separates the source from the sink.
///
/// In image segmentation applications:
/// - `Source` typically represents the foreground/object
/// - `Sink` typically represents the background
///
/// # Examples
///
/// ```rust,no_run
/// use grid_cut_rs::{GridGraph2D4C, Segment};
///
/// # fn main() -> Result<(), Box<dyn std::error::Error>> {
/// let mut graph = GridGraph2D4C::<i32, i32, i32>::new(10, 10)?;
/// // ... set up capacities ...
/// graph.compute_maxflow();
///
/// let node = graph.node_id(5, 5)?;
/// let segment = graph.get_segment(node);
///
/// match segment {
///     Segment::Source => println!("Node is in foreground"),
///     Segment::Sink => println!("Node is in background"),
/// }
/// # Ok(())
/// # }
/// ```
#[derive(Debug, Clone, Copy, PartialEq, Eq)]
pub enum Segment {
    /// Node belongs to source segment (typically foreground/object)
    Source = 0,
    /// Node belongs to sink segment (typically background)
    Sink = 1,
}

/// Internal node label during algorithm execution
#[derive(Debug, Clone, Copy, PartialEq, Eq)]
pub(crate) enum Label {
    /// Node not yet assigned to a tree
    Free = 0,
    /// Node belongs to source tree
    Source = 1,
    /// Node belongs to sink tree
    Sink = 2,
}

/// Parent edge direction for 2D 4-connected grids
#[derive(Debug, Clone, Copy, PartialEq, Eq)]
pub(crate) enum Parent {
    /// Parent in +X direction (right): [+1, 0]
    GreaterX = 0,
    /// Parent in +Y direction (down): [0, +1]
    GreaterY = 1,
    /// Parent in -Y direction (up): [0, -1]
    LessY = 2,
    /// Parent in -X direction (left): [-1, 0]
    LessX = 3,
    /// No parent (orphan node)
    None = 4,
    /// Parent is terminal (source or sink)
    Terminal = 5,
}

impl Parent {
    /// Returns the sister (reverse) direction
    #[inline]
    pub(crate) fn sister(self) -> Self {
        match self {
            Parent::GreaterX => Parent::LessX,
            Parent::GreaterY => Parent::LessY,
            Parent::LessY => Parent::GreaterY,
            Parent::LessX => Parent::GreaterX,
            Parent::None => Parent::None,
            Parent::Terminal => Parent::Terminal,
        }
    }
}

/// Parent edge direction for 2D 8-connected grids
#[derive(Debug, Clone, Copy, PartialEq, Eq)]
pub(crate) enum Parent8 {
    /// Parent in +X direction: [+1, 0]
    GreaterX = 0,
    /// Parent in +Y direction: [0, +1]
    GreaterY = 1,
    /// Parent in -Y direction: [0, -1]
    LessY = 2,
    /// Parent in -X direction: [-1, 0]
    LessX = 3,
    /// Parent in diagonal +X+Y: [+1, +1]
    GreaterXGreaterY = 4,
    /// Parent in diagonal +X-Y: [+1, -1]
    GreaterXLessY = 5,
    /// Parent in diagonal -X+Y: [-1, +1]
    LessXGreaterY = 6,
    /// Parent in diagonal -X-Y: [-1, -1]
    LessXLessY = 7,
    /// No parent (orphan node)
    None = 8,
    /// Parent is terminal (source or sink)
    Terminal = 9,
}

/// Parent edge direction for 3D 6-connected grids
#[derive(Debug, Clone, Copy, PartialEq, Eq)]
pub(crate) enum Parent3D {
    /// Parent in +X direction: [+1, 0, 0]
    GreaterX = 0,
    /// Parent in +Y direction: [0, +1, 0]
    GreaterY = 1,
    /// Parent in +Z direction: [0, 0, +1]
    GreaterZ = 2,
    /// Parent in -Z direction: [0, 0, -1]
    LessZ = 3,
    /// Parent in -Y direction: [0, -1, 0]
    LessY = 4,
    /// Parent in -X direction: [-1, 0, 0]
    LessX = 5,
    /// No parent (orphan node)
    None = 6,
    /// Parent is terminal (source or sink)
    Terminal = 7,
}

impl Parent3D {
    /// Returns the sister (reverse) direction
    #[inline]
    pub(crate) fn sister(self) -> Self {
        match self {
            Parent3D::GreaterX => Parent3D::LessX,
            Parent3D::GreaterY => Parent3D::LessY,
            Parent3D::GreaterZ => Parent3D::LessZ,
            Parent3D::LessZ => Parent3D::GreaterZ,
            Parent3D::LessY => Parent3D::GreaterY,
            Parent3D::LessX => Parent3D::GreaterX,
            Parent3D::None => Parent3D::None,
            Parent3D::Terminal => Parent3D::Terminal,
        }
    }
}

/// Parent edge direction for 3D 26-connected grids
#[derive(Debug, Clone, Copy, PartialEq, Eq)]
pub(crate) enum Parent3D26 {
    // Face neighbors (6)
    /// Parent in +X direction: [+1, 0, 0]
    GreaterX = 0,
    /// Parent in +Y direction: [0, +1, 0]
    GreaterY = 1,
    /// Parent in +Z direction: [0, 0, +1]
    GreaterZ = 2,
    /// Parent in -Z direction: [0, 0, -1]
    LessZ = 3,
    /// Parent in -Y direction: [0, -1, 0]
    LessY = 4,
    /// Parent in -X direction: [-1, 0, 0]
    LessX = 5,
    
    // Edge neighbors (12)
    /// Parent in +X+Y direction: [+1, +1, 0]
    GreaterXGreaterY = 6,
    /// Parent in +X-Y direction: [+1, -1, 0]
    GreaterXLessY = 7,
    /// Parent in -X+Y direction: [-1, +1, 0]
    LessXGreaterY = 8,
    /// Parent in -X-Y direction: [-1, -1, 0]
    LessXLessY = 9,
    /// Parent in +X+Z direction: [+1, 0, +1]
    GreaterXGreaterZ = 10,
    /// Parent in +X-Z direction: [+1, 0, -1]
    GreaterXLessZ = 11,
    /// Parent in -X+Z direction: [-1, 0, +1]
    LessXGreaterZ = 12,
    /// Parent in -X-Z direction: [-1, 0, -1]
    LessXLessZ = 13,
    /// Parent in +Y+Z direction: [0, +1, +1]
    GreaterYGreaterZ = 14,
    /// Parent in +Y-Z direction: [0, +1, -1]
    GreaterYLessZ = 15,
    /// Parent in -Y+Z direction: [0, -1, +1]
    LessYGreaterZ = 16,
    /// Parent in -Y-Z direction: [0, -1, -1]
    LessYLessZ = 17,
    
    // Corner neighbors (8)
    /// Parent in +X+Y+Z direction: [+1, +1, +1]
    GreaterXGreaterYGreaterZ = 18,
    /// Parent in +X+Y-Z direction: [+1, +1, -1]
    GreaterXGreaterYLessZ = 19,
    /// Parent in +X-Y+Z direction: [+1, -1, +1]
    GreaterXLessYGreaterZ = 20,
    /// Parent in +X-Y-Z direction: [+1, -1, -1]
    GreaterXLessYLessZ = 21,
    /// Parent in -X+Y+Z direction: [-1, +1, +1]
    LessXGreaterYGreaterZ = 22,
    /// Parent in -X+Y-Z direction: [-1, +1, -1]
    LessXGreaterYLessZ = 23,
    /// Parent in -X-Y+Z direction: [-1, -1, +1]
    LessXLessYGreaterZ = 24,
    /// Parent in -X-Y-Z direction: [-1, -1, -1]
    LessXLessYLessZ = 25,
    
    /// No parent (orphan node)
    None = 26,
    /// Parent is terminal (source or sink)
    Terminal = 27,
}
